package com.learning.lesson16graph;

import com.common.utils.ArrayUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 图
 *
 * @author Zongheng Ma
 * @date 2020/8/17
 */
public class Graph {

    public static void main(String[] args) {
        String[] vertexArr = {"1", "2", "3", "4", "5", "6", "7", "8"};
        Graph graph = new Graph(vertexArr.length);
        for (String v : vertexArr) {
            graph.addVertex(v);
        }
        // 添加边
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 2, 1);
        graph.addEdge(1, 3, 1);
        graph.addEdge(1, 4, 1);
        graph.addEdge(3, 7, 1);
        graph.addEdge(4, 7, 1);
        graph.addEdge(2, 5, 1);
        graph.addEdge(2, 6, 1);
        graph.addEdge(5, 6, 1);
        // 深度优先
        System.out.println("深度优先搜索：");
        graph.dfs(0);
        // 广度优先
        System.out.println("广度优先搜索：");
        graph.bfs(0);
    }

    /**
     * 顶点集合
     */
    private final List<String> vertexList;

    /**
     * 邻接矩阵
     */
    private final int[][] edges;

    /**
     * 记录对应下标的顶点是否已被访问
     */
    private final boolean[] isVisited;


    /**
     * 边的个数
     */
    private int edgeNum;

    /**
     * 构造器
     *
     * @param n 边个数
     */
    public Graph(int n) {
        this.edgeNum = n;
        this.isVisited = new boolean[n];
        this.edges = new int[n][n];
        this.edgeNum = 0;
        vertexList = new ArrayList<>(n);
    }


    /**
     * 获取边个数
     *
     * @return
     */
    public int getEdgeNum() {
        return edgeNum;
    }


    /**
     * 获取顶点个数
     *
     * @return
     */
    public int getVertexNum() {
        return vertexList.size();
    }


    /**
     * 添加顶点
     *
     * @param vertex 新顶点
     */
    public void addVertex(String vertex) {
        if (vertexList.size() == edges.length) {
            System.out.println("顶点数量已达上限！");
            return;
        }
        vertexList.add(vertex);
    }


    /**
     * 添加边
     *
     * @param v1     起点在邻接矩阵的下标
     * @param v2     终点在邻接矩阵的下标
     * @param weight 边的权
     */
    public void addEdge(int v1, int v2, int weight) {
        if (v1 + 1 > vertexList.size()) {
            System.out.println("起点不存在！");
            return;
        }
        if (v2 + 1 > vertexList.size()) {
            System.out.println("顶点不存在！");
            return;
        }
        /*
         * 无向图顶点的连接时相互的
         * 同一个边在连接矩阵中需要添加两次记录
         * 两个记录在矩阵中位置关于对角线对称
         */
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        edgeNum += 1;
    }


    /**
     * 对应下标的顶点是否被访问
     *
     * @param index 顶点下标
     * @return
     */
    public boolean notVisited(int index) {
        return !isVisited[index];
    }


    /**
     * 标记对应下标顶点为已访问
     *
     * @param index 顶点下标
     */
    public void visitVertex(int index) {
        isVisited[index] = true;
    }


    /**
     * 寻找当前顶点的第一个邻接顶点
     *
     * @param index 当前顶点的下标
     * @return
     */
    public int findFirstNeighbor(int index) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 寻找下一个邻接顶点
     *
     * @param index 当前节点的下标
     * @param last  上一个邻接顶点的下标
     * @return
     */
    public int findNextNeighbor(int index, int last) {
        for (int i = last + 1; i < vertexList.size(); i++) {
            if (edges[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 根据下标获取顶点
     *
     * @param index 顶点下标
     * @return
     */
    public String getVertex(int index) {
        return vertexList.get(index);
    }


    /**
     * 显示图对应的矩阵
     */
    public void showMatrix() {
        ArrayUtils.print2DeArray(edges);
    }


    /**
     * 深度优先搜索
     *
     * @param i         当前顶点下标
     * @param isVisited 各顶点访问情况
     */
    private void dfs(int i, boolean[] isVisited) {
        if (i >= vertexList.size()) {
            return;
        }

        if (!isVisited[i]) {
            // 访问该顶点
            System.out.println(getVertex(i));
            // 设置已访问标识
            isVisited[i] = true;
        }

        // 查找当前顶点的第一个邻接顶点
        int w = findFirstNeighbor(i);
        while (w >= 0) {
            if (!isVisited[w]) {
                dfs(w, isVisited);
            }
            w = findNextNeighbor(i, w);
        }
    }


    /**
     * 深度优先搜索
     *
     * @param i 开始遍历的顶点下标
     */
    public void dfs(int i) {
        // 记录访问情况
        boolean[] isVisited = new boolean[vertexList.size()];
        // 从当前顶点开始深度优先搜索
        for (int j = i; j < vertexList.size(); j++) {
            if (!isVisited[j]) {
                dfs(j, isVisited);
            }
        }
        // 初始顶点不是下标0的顶点，则从头深度优先搜索
        if (i > 0) {
            for (int j = 0; j < i; j++) {
                if (!isVisited[j]) {
                    dfs(j, isVisited);
                }
            }
        }
    }


    /**
     * 广度优先搜索
     *
     * @param isVisited 顶点访问情况
     * @param i         当前顶点下标
     */
    private void bfs(boolean[] isVisited, int i) {
        LinkedList<Integer> queue = new LinkedList<>();
        // 访问初始顶点
        if (!isVisited[i]) {
            System.out.println(vertexList.get(i));
            isVisited[i] = true;
            queue.add(i);
        }
        // 队头顶点下标
        int u;
        // 第一个邻接顶点下标
        int w;
        while (!queue.isEmpty()) {
            // 队头出队
            u = queue.removeFirst();
            // 寻找第一个邻接顶点
            w = findFirstNeighbor(u);
            // 找到了邻接顶点
            while (w >= 0) {
                // 访问邻接顶点
                if (!isVisited[w]) {
                    System.out.println(vertexList.get(w));
                    isVisited[w] = true;
                    queue.add(w);
                }
                // 寻找下一个邻接顶点
                w = findNextNeighbor(u, w);
            }
        }
    }


    /**
     * 广度优先搜索
     *
     * @param i 开始访问的下标
     */
    public void bfs(int i) {
        boolean[] isVisited = new boolean[vertexList.size()];
        for (int j = i; j < vertexList.size(); j++) {
            bfs(isVisited, j);
        }
        if (i > 0) {
            for (int j = 0; j < i; j++) {
                bfs(isVisited, j);
            }
        }
    }
}
